package cn.antblog.sort;

/**
 * @author yangjy
 * @date 2020/8/18 13:01
 */
public class MyTest {
    //1!+2! +++ n!
    public static int fact1(int n ){
        int i,j,temp,s;
        s=0;
        for (i = 1;i<=n;i++){
            temp = 1;
            for (j=1;j<=i;j++){
                temp = temp*j;
            }
            s= s+temp;
        }
        return s;
    }

    //1!+2! +++ n!
    public static int fact2(int n ){
        int i,temp,s;
        s=0;
        temp = 1;
        for (i = 1;i<=n;i++){
            temp = temp*i;
            s= s+temp;
        }
        return s;
    }


    //插入排序
    public static void insertSort(){
        /* 插入排序*/
        int num[] = {3, 7, 1, 8, 5};
        int pos, cur;
        int i;
        //int length = sizeof(num)/sizeof(num[0]);

        for (i = 1; i < num.length; i++)
        {
            pos = i -1 ;    //有序序列的最后一个元素位置
            cur = num[i];    //保存待排序元素的值
            //找位置
            while ( pos >= 0 && num[pos] > cur)
            {
                num[pos + 1] = num[pos];
                pos--;
            }
            num[pos + 1] = cur;    //将待排序元素插入数组中
           /* for(int j = 0;j<num.length;j++){
                System.out.print(num[j]);
            }*/
        }
    }


    //*********************快速排序***********************************

    private static void quickSort(int[] arr, int low, int high) {
       // int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 };
        if (low < high) {
            // 找寻基准数据的正确索引
            int index = getIndex(arr, low, high);

            // 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
            quickSort(arr, low, index - 1); // // 排序tmp左边
            quickSort(arr, index + 1, high);// // 排序tmp右边
        }

    }

    private static int getIndex(int[] arr, int low, int high) {
        // int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 };
        // 基准数据
        int tmp = arr[low];
        while (low < high) {
            // 当队尾的元素大于等于基准数据时,向前挪动high指针
            while (low < high && arr[high] >= tmp) {
                high--;
            }
            // 如果队尾元素小于tmp了,需要将其赋值给low
            arr[low] = arr[high];
            // 当队首元素小于等于tmp时,向前挪动low指针
            while (low < high && arr[low] <= tmp) {
                low++;
            }
            // 当队首元素大于tmp时,需要将其赋值给high
            arr[high] = arr[low];

        }
        // 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
        // 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]
        arr[low] = tmp;
        return low; // 返回tmp的正确位置
    }
    //*********************快速排序***********************************


    //**************************选择直接排序************************************&*
    public static void zjSelectSort(){
        int list[] = {5,23,86,21,43,67,45,34,58,23,102,123,11,22,1};
        int i, j, temp,min;
        for(i = 0; i< 15;i++)
        {
            //令最小值等于无序区的第一个值
            min = list[i];
            temp = i;
            //找到无序区的最小值
            for(j = i; j<15;j++)
            {
                if(min>list[j])
                {
                    temp = j;
                    min = list[j];
                }

            }
            //交换
            list[temp] = list[i];

            list[i] = min;
            temp = 0;

        }
        for (i = 0;i < 15; i++){
            System.out.print(list[i]+"|");
        }
    }

    //**************************选择直接排序************************************&*




    public static void main(String[] args) {
        //int i = fact2(10);
       // System.out.println(i);

        //insertSort();插入排序
        int[] arr = { 12,85,25,16,34,23,49,95,17,61 };
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序后:");
        for (int i : arr) {
            System.out.print(i+"|");
        }

        //zjSelectSort();
    }
}
